Лексикографический порядок на множестве и его свойства

Для $a = (a_1, \dots, a_k), \ b = (b_1, \dots, b_k) \in \mathbb{N}^k$ выполняется **лексикографический порядок** $a \leq_{L} b$ тогда и только тогда, когда: - либо $a = b$ - либо $\exists{i \leq k}\mathpunct{:}~~ (\forall{j < i}\mathpunct{:}~~ a_{j} = b_{j}) \land a_{i} < b_{i}$ Пример для понимания: $(1, 2, 3, 4) \leq_{L} (1, 2, 5, 1)$

$\leq_L$ - отношение частичного порядка и $\forall{a, b}\mathpunct{:}$ $a$ и $b$ сравнимы

**Частичный порядок** Отношение является частичным порядком, если оно *рефлексивно*, *антисимметрично* и *транзитивно*. *Рефлексивность* Очевидно, так как $a = a$ *Антисимметричность* Хотим: $a \leq_{L} b \land b \leq_{L} a \implies a = b$ От противного: $a \neq b$. По определению: $$\begin{align} \exists{i \leq k}\mathpunct{:}~~& (\forall{j < i}\mathpunct{:}~~ a_{j} = b_{j}) \land a_{i} < b_{i} \\ \exists{m \leq k}\mathpunct{:}~~& (\forall{j < m}\mathpunct{:}~~ b_{j} = a_{j}) \land b_{m} < a_{m} \end{align}$$ Если $i = m$, то $a_{i} < b_{i} < a_{i}$, противоречие. Пусть $i \neq m$. Без ограничения общности, $i < m$. Из первой строки получаем $a_{i} < b_{i}$, из второй - $a_{i} = b_{i}$. Противоречие. *Транзитивность* Хотим: $a \leq_{L} b \land b \leq_{L} c \implies a \leq_{L} c$ Если $a = b$, утверждение очевидно. Пусть $a \neq b$. Тогда по определению: $$\begin{align} \exists{i \leq k}\mathpunct{:}~~& (\forall{j < i}\mathpunct{:}~~ a_{j} = b_{j}) \land a_{i} < b_{i} \\ \exists{m \leq k}\mathpunct{:}~~& (\forall{j < m}\mathpunct{:}~~ b_{j} = c_{j}) \land b_{m} < c_{m} \end{align}$$ Если $i = m$, то $a_{i} < b_{i} < c_{i}$ Если $i < m$, то $a_{i} < b_{i} = c_{i}$ Если $i > m$, то $a_{m} = b_{m} < c_{m}$ Следовательно, транзитивность выполняется. **Сравнимость** Если $a = b$, то $a$ и $b$ сравнимы по определению. Пусть $a \neq b$. Возьмём минимальный $i$ такой, что $a_{i} \neq b_{i}$. Значит $\forall{j < i}\mathpunct{:}~~ a_{j} = b_{j}$. Собирая всё вместе, получаем определение лексикографического порядка. $\square$

Пусть $\varnothing \neq S \subset \mathbb{N}^{k}$. Тогда в $S$ есть минимальный элемент.

Обозначим взятие $i$-го элемента из кортежа как $a[i]$. Тогда: $$\begin{align} n_{1} &= \min \{a[0] \mid a \in S\} \\ S_{1} &= \{a \in S \mid a[0] = n_{1} \} \\ n_{2} &= \min \{a[1] \mid a \in S\} \\ S_{2} &= \{a \in S \mid a[1] = n_{2} \} \\ \dots & \end{align}$$ Продолжая процесс, получим $(n_{1}, n_{2}, \dots, n_{k}) \in S$. Ясно, что это минимальный элемент. $\square$